Was ist horner schema?

Das Horner-Schema, auch Horner-Algorithmus oder Horner-Methode genannt, ist ein effizientes Verfahren zur Auswertung von Polynomen in einer gegebenen Variable. Es wird auch zur Division eines Polynoms durch einen linearen Faktor der Form x - a verwendet.

Kernidee:

Das Horner-Schema basiert auf der Umformung eines Polynoms in eine verschachtelte Form. Betrachten wir das Polynom:

p(x) = aₙxⁿ + aₙ₋₁xⁿ⁻¹ + ... + a₁x + a₀

Dies kann umgeformt werden zu:

p(x) = a₀ + x(a₁ + x(a₂ + ... + x(aₙ₋₁ + xaₙ)...))

Vorgehensweise zur Auswertung:

Um p(x) für einen bestimmten Wert von x (nennen wir ihn x₀) auszuwerten, geht man wie folgt vor:

Setze bₙ = aₙ
Für i = n-1, n-2, ..., 0: berechne bᵢ = aᵢ + x₀ * bᵢ₊₁
Das Ergebnis ist b₀, d.h. p(x₀) = b₀

Vorteile:

Effizienz: Das Horner-Schema reduziert die Anzahl der Multiplikationen und Additionen im Vergleich zur direkten Auswertung des Polynoms. Dies ist besonders vorteilhaft für Polynome hohen Grades.
Stabilität: In vielen Fällen ist das Horner-Schema numerisch stabiler als andere Auswertungsmethoden.
Division von Polynomen: Das Horner-Schema kann verwendet werden, um ein Polynom durch einen linearen Faktor (x-a) zu dividieren. Die Koeffizienten des Quotienten sind die berechneten bᵢ-Werte (ohne b₀), und b₀ ist der Rest der Division.

Anwendungen:

Polynomauswertung: Die primäre Anwendung ist die schnelle und effiziente Berechnung des Wertes eines Polynoms an einem gegebenen Punkt.
Division von Polynomen: Finden des Quotienten und Rests bei der Division durch einen linearen Faktor.
Nullstellenfindung: Das Horner-Schema wird in einigen Algorithmen zur Nullstellenfindung verwendet, z.B. in Kombination mit der Newton-Methode.
Basisumwandlung: Das Horner-Schema kann verwendet werden, um eine Zahl von einer Basis in eine andere umzuwandeln.

Beispiel:

Betrachten wir das Polynom p(x) = 2x³ - x² + 3x - 4 und wir wollen p(2) berechnen: